package com.zhanghp.class07;

/**
 * <h1>归并排序</h1>
 * 时间上打败左神，空间上和左神持平
 * <a href = "https://leetcode.cn/problems/sort-an-array/">leetcode</a>
 *
 * @author zhanghp
 * @since 2024/2/1 9:43
 */
public class Code01_MergeSort_Recursion {

    public int[] mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        int L = 0;
        int R = arr.length - 1;
        return process(arr, L, R);
    }

    public int[] process(int[] arr, int L, int R) {
        if (R - L == 0) {
            return new int[]{arr[L]};
        }
        int mid = getMid(L, R);
        int[] leftArr = process(arr, L, mid);
        int[] rightArr = process(arr, mid + 1, R);
        return merge(leftArr, rightArr);
    }

    public int[] merge(int[] left, int[] right) {
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        // 开始比较
        int size = left.length + right.length;
        int[] arr = new int[size];
        int lIndex = 0;
        int rIndex = 0;
        for (int i = 0; i < size; i++) {
            if (lIndex >= left.length) {
                copy(right, rIndex, arr, i);
                break;
            }
            if (rIndex >= right.length) {
                copy(left, lIndex, arr, i);
                break;
            }
            arr[i] = left[lIndex] <= right[rIndex] ? left[lIndex++] : right[rIndex++];
        }
        return arr;
    }

    public void copy(int[] source, int sStart, int[] destination, int dStart) {
        for (int i = dStart; i < destination.length; i++) {
            destination[i] = source[sStart++];
        }
    }

    private int getMid(int L, int R) {
        return L + ((R - L) >> 1);
    }
}
